/**
 * 20220119：finalized by jordia
 */
import BvhStrategy from "./bvh-strategy";
import BvhNode from './bvh-node';
import Method from "../../common/method";

/**
 * 层次包围盒树
 */
export default class BvhTree {
    constructor() {
        this._root = null;
        this._numLeaves = 0;
        this._strategy = new BvhStrategy();
        this._nodePool = null;
        this.leafList = null;
        this.leafListLast = null;
        this.tmp = new Array(1024);
    }
    _getBalance() {
        return this.getBalanceRecursive(this._root);
    }
    _resetRoot(root){
        root._children[0] = root._children[1] = null;
        root._childIndex = 0;
        root._parent = null;
        root._height = 0;
        root._proxy = null;
        root._next = this._nodePool;
        this._nodePool = root;
    }
    deleteRecursive(root) {
        if(root._height === 0) {
            let prev = root._prevLeaf, next = root._nextLeaf;
            if(prev != null) prev._nextLeaf = next;
            if(next != null) next._prevLeaf = prev;
            if(root === this.leafList) this.leafList = this.leafList._nextLeaf;
            if(root === this.leafListLast) this.leafListLast = this.leafListLast._prevLeaf;
            root._nextLeaf = root._prevLeaf = null;
            root._proxy._leaf = null;
            this._resetRoot(root);
            return;
        }
        this.deleteRecursive(root._children[0]);
        this.deleteRecursive(root._children[1]);
        this._resetRoot(root);
    }
    decomposeRecursive(root) {
        if(root._height === 0) {
            root._childIndex = 0;
            root._parent = null;
            return;
        }
        this.decomposeRecursive(root._children[0]);
        this.decomposeRecursive(root._children[1]);
        this._resetRoot(root);
    }
    buildTopDownRecursive(leaves,from,until) {
        if(until - from === 1) {
            let leaf = leaves[from];
            let proxy = leaf._proxy;
            let le=leaf.size,pe=proxy.size;
            Method.copyElements(pe,le,0,0,6);
            return leaf;
        }
        let splitAt = this._strategy._splitLeaves(leaves,from,until);
        let child1 = this.buildTopDownRecursive(leaves,from,splitAt);
        let child2 = this.buildTopDownRecursive(leaves,splitAt,until);
        let first = this._nodePool;
        if(first != null) {
            this._nodePool = first._next;
            first._next = null;
        } else {
            first = new BvhNode();
        }
        let parent = first;
        parent._children[0] = child1;
        child1._parent = parent;
        child1._childIndex = 0;
        parent._children[1] = child2;
        child2._parent = parent;
        child2._childIndex = 1;
        let c1 = parent._children[0].size, c2 = parent._children[1].size,pe=parent.size;
        Method.boxUnionBox(c1,c2,pe);
        let h1 = parent._children[0]._height, h2 = parent._children[1]._height;
        parent._height = (h1 > h2 ? h1 : h2) + 1;
        return parent;
    }
    getBalanceRecursive(root) {
        if(root == null || root._height === 0) {
            return 0;
        }
        let balance = root._children[0]._height - root._children[1]._height;
        if(balance < 0) {
            balance = -balance;
        }
        return balance + this.getBalanceRecursive(root._children[0]) + this.getBalanceRecursive(root._children[1]);
    }
}